package msb.class06;

import org.junit.Test;

/******************************************************************************
 * https://leetcode.cn/problems/count-of-range-sum/
 * 问题
 * 区间和的个数
 * 给你一个整数数组nums 以及两个整数lower 和 upper 。
 * 求数组中，值位于范围 [lower, upper] （包含lower和upper）之内的 区间和的个数 。
 * 区间和S(i, j)表示在nums中，位置从i到j的元素之和，包含i和j(i ≤ j)。
 * *****************************************************************************
 * *****************************************************************************
 *
 * 思路
 * 死办法 时间复杂度 O(N^3)
 *
 * 关键点1 -> 前缀数组sum ->减少一个N的复杂度
 * sum[i] = S(0,i)
 * S(i,j) = S(0,j) - S(0,i-1) = sum[j] - sum[i]
 *
 * 关键点2 -> 数据间的关系
 * S(i,j) = [lower,upper]
 * sum[j] - sum[i] = [lower,upper]
 * sum[i] = [sum[j]-upper,sum[j]-lower]
 *
 * 关键点3 -> 内部有序 -> 归并算法
 * 给定sum[j] 确定sum[i]的范围值
 * sum[j]保证有序，sum[i]的范围最大值与最小值分别有序
 *
 */
public class Code01_CountOfRangeSum {

    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums.length == 0) {
            return 0;
        }
        //前缀数组 O[N]
        long sum[] = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        return process(sum, 0, nums.length - 1, lower, upper);
    }


    public static int process(long[] sum, int L, int R, int lower, int upper) {
        if (L == R) {
            if (sum[L] >= lower && sum[L] <= upper) {
                return 1;
            } else {
                return 0;
            }
        }
        int count = 0;

        int mid = L + ((R - L) >> 1);
        count += process(sum, L, mid, lower, upper);
        count += process(sum, mid + 1, R, lower, upper);
        count += count(sum, L, mid, R, lower, upper);
        merge(sum, L, mid, R);
        return count;
    }

    public static int count(long[] sum, int L, int mid, int R, int lower, int upper) {
        //[leftStartPoint,leftEndPoint)
        int leftStartPoint = L;
        int leftEndPoint = L;
        int rightPoint = mid + 1;
        int count = 0;
        while (rightPoint <= R) {
            while (leftStartPoint <= mid && sum[leftStartPoint] < sum[rightPoint] - upper) {
                leftStartPoint++;
            }
            while (leftEndPoint <= mid && sum[leftEndPoint] <= sum[rightPoint] - lower) {
                leftEndPoint++;
            }
            count += leftEndPoint - leftStartPoint;
            rightPoint++;
        }
        return count;
    }

    //L..mid 与 mid+1..R进行归并
    public static void merge(long[] sum, int L, int mid, int R) {
        int leftPoint = L;
        int rightPoint = mid + 1;
        long[] tmpArr = new long[R - L + 1];
        int tmpPoint = 0;

        //左右指针越界，归并完整
        while (leftPoint <= mid || rightPoint <= R) {
            //左边指针越界，左边归并完毕，直接取右指针值
            if (leftPoint > mid) {
                tmpArr[tmpPoint++] = sum[rightPoint++];
                continue;
            }
            //右边指针越界，右边归并完毕，直接取左指针值
            if (rightPoint > R) {
                tmpArr[tmpPoint++] = sum[leftPoint++];
                continue;
            }

            //两边都没有越界，取最小值
            if (sum[leftPoint] <= sum[rightPoint]) {
                tmpArr[tmpPoint++] = sum[leftPoint++];
            } else {
                tmpArr[tmpPoint++] = sum[rightPoint++];
            }
        }

        for (int i = 0; i < tmpArr.length; i++) {
            sum[L + i] = tmpArr[i];
        }
    }


    /**
     * 暴力破解
     *
     * @return
     */
    public int countRangeSum1(int[] nums, int lower, int upper) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= i; j++) {
                long sum = 0;
                for (int k = j; k <= i; k++) {
                    sum += nums[k];
                }
                if (sum >= lower && sum <= upper) {
                    count++;
                }
            }
        }
        return count;
    }

    @Test
    public void test() {
        int[] nums = new int[]{2147483647,-2147483648,-1,0};
        int lower = -1;
        int upper = 0;
        Code01_CountOfRangeSum code = new Code01_CountOfRangeSum();
        System.out.println(code.countRangeSum(nums, lower, upper));
    }


}
